// https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree/description

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode * root) {
        // queue<TreeNode *> q; 用queue既要存储又要bfs有点麻烦
        // q.push(root);
        // for (int i = 0; i < q.size(); ++i)
        // {
        //     TreeNode* tmp = q.front();
        //     if (tmp)
        //     {
        //         q.push(tmp->left);
        //         q.push(tmp->right);
        //     }
        // }
        vector<TreeNode *> q;
        q.push_back(root);
        for (int i = 0; i < q.size(); ++i)
        {
            TreeNode* tmp = q[i];
            if (tmp)
            {
                q.push_back(tmp->left);
                q.push_back(tmp->right);
            }
        }
        while (!q.empty() && q.back() == NULL)
        {
            q.pop_back();
        }
        if (q.empty()) return "{}";
        stringstream ss;
        ss << "{" << q[0]->val;
        for (int i = 1; i < q.size(); ++i)
        {
            TreeNode * tmp = q[i];
            if (!tmp) ss << ", #";
            else ss << ", " << tmp->val;
        }
        ss << "}";
        return ss.str();
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode * deserialize(string &data) {
        if (data == "{}") return NULL;
        vector<string> vals = split(data.substr(1, data.size() - 2), ",");
        TreeNode * root = new TreeNode(stoi(vals[0]));
        queue<TreeNode *> q;
        q.push(root);
        bool isLeft = true;
        for (int i = 1; i < vals.size(); ++i)
        {
            if (vals[i] != "#")
            {
                TreeNode * node = new TreeNode(stoi(vals[i]));
                if (isLeft) q.front()->left = node;
                else q.front()->right = node;
                q.push(node);
            }
            if (!isLeft) q.pop();
            isLeft = !isLeft;
        }
        return root;
    }
};


// 个
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode * root) {
        vector<TreeNode *> q;
        string result = "{";
        q.push_back(root);
        for (int i = 0; i < q.size(); ++i) //注意是层序不是前序
        {
            TreeNode * tmp = q[i];
            if (tmp) //注意！
            {
                q.push_back(tmp->left);
                q.push_back(tmp->right);
            }
        }
        while (!q.empty() && q.back() == NULL) //重要！
        {
            q.pop_back();
        }
        for (int i = 0; i < q.size(); ++i)
        {
            TreeNode * root = q[i];
            if (root) result += to_string(root->val);
            else result += "#";
            if (i != q.size() - 1) result += ",";
        }
        result += "}";
        return result;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode * deserialize(string &data) {
        if (data == "{}") return NULL;
        string tmp = "";
        int idx = data.find(",");
        TreeNode * root = new TreeNode(stoi(data.substr(1, idx - 1)));
        queue<TreeNode *> q;
        q.push(root);
        bool isLeft = true;
        for (int i = idx + 1; i < data.size(); ++i)
        {
            TreeNode * node = NULL;
            if (data[i] == ',' || data[i] == '}')
            {
                if (tmp != "") node = new TreeNode(stoi(tmp));
                if (isLeft) 
                {   
                    q.front()->left = node;
                }
                else 
                {
                    q.front()->right = node;
                    q.pop();
                }
                if (node) q.push(node);
                isLeft = !isLeft;
                tmp = "";
            }
            else if (data[i] != '#')
            {
                tmp += data[i];
            }
        }
        return root;
    }
};



// https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/submissions/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "[]";
        queue<TreeNode*> q;
        string res = "[";
        q.push(root);
        res += to_string(root->val);
        while (!q.empty()) {
            // int len = q.size();
            // for (int i = 0; i < len; ++i) { 加不加都行
                TreeNode* tmp = q.front();
                q.pop();
                if (tmp) {
                    if (tmp != root) {
                        res += ',';
                        res += to_string(tmp->val);
                    }
                    q.push(tmp->left);
                    q.push(tmp->right);
                } else {
                    res += ",null";
                }
            // }
        }
        return res + ']';
    } // 后面有多的null没关系，反序列化的时候能恢复就行

    vector<string> split(string input, char del) {
        int pos = 0;
        vector<string> res;
        string tmp = "";
        while (pos < input.length()) {
            if (input[pos] == del) {
                res.push_back(tmp);
                tmp = "";
            } else {
                tmp += input[pos];
            }
            ++pos;
        }
        return res;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> vals = split(data.substr(1, data.size() - 2), ',');
        if (vals.empty()) return NULL;
        TreeNode* root = new TreeNode(stoi(vals[0]));
        queue<TreeNode*> q;
        q.push(root);
        bool isLeft = true;
        for (int i = 1; i < vals.size(); ++i) {
            if (vals[i] != "null") {
                TreeNode* node = new TreeNode(stoi(vals[i]));
                if (isLeft) q.front()->left = node;
                else q.front()->right = node;
                q.push(node);
            }
            if (!isLeft) q.pop();
            isLeft = !isLeft;
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));